Міністерство освіти і науки, молоді та спорту України
Національний університет „Львівська політехніка”
Звіт
з лабораторної роботи № 4
з дисципліни: “Програмування (частина 3)”
на тему: “ Структура даних Черга ”
Мета роботи: Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач.
Постановка задачі: Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Переписати основні операції для роботи з чергою (push, pop, front, empty, full) або деком (push_left, push_right, pop_left, pop_right, front_left, front_right, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності.
Змоделювати циклічну чергу, в якій реалізований такий механізм додавання нового елемента: якщо досягнутий кінець масиву, то новий елемент додається в перший елемент масиву, якщо це можливо. Після обробки всієї заданої вхідної послідовності перевірити, чи всі числа у черзі будуть парними, чи ні.
Алгоритм розв’язання задачі:
main.cpp
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <windows.h>
const int CAPACITY=5;
using namespace std;
template <typename _data>
class queue{
_data array [CAPACITY];
int first;
int last;
int size;
public:
queue(void)
{
size=0, first=0,last=-1;
for(int i=0;i<CAPACITY;++i)
array[i]=0;
}
int get_first(void){return first;}
int get_last(void){ return last;}
int get_size(void){ return size;}
void push (int x)
{
if(size<CAPACITY)
{
last++,size++;
if(last==CAPACITY)
last=0;
array[last]=x;
}
else cerr<<"Error: Queue is full!"<<endl;
}
void pop(void)
{
if(size!=0)
{
first++,size--;
if(first==CAPACITY)
first=0;
}
else cerr<<"Error: Queue is empty!"<<endl;
}
_data front (void) {return data[first];}
bool empty(void){ return size ;}
void show (void);
void show_array(void);
};
template<typename data>
void queue <data>::show(void){
for(int i=first, j=0; j<size;++i, ++j)
{
if(i==CAPACITY)
i=0;
cout<<array[i]<<' ';
if(i==last)
break;
}
cout<<endl;
}
int main()
{
setlocale(LC_ALL,"ukr");
queue <int> object;
cout<<"Тестування циклiчної черги."<<endl;
cout<<"Введiть додатнi числа для додавання їх до черги, вiд'ємнi для виштовхування числа з черги або нуль для виходу."<<endl;
while(true)
{
int number;
cout<<"К = ";
cin>>number;
if(number<0)
object.pop();
else if(number>0) object.push(number);
else break;
cout<<endl<<"Стан черги: ";
object.show();
cout<<endl<<"Iндекс першого елемента "<<object.get_first()<<endl;
cout<<"Iндекс останнього елемента "<<object.get_last()<<endl;
cout<<"Розмiр черги "<<object.get_size()<<endl<<endl;
}
}
Результати виконання програми:
Висновок:
В результаті виконання лабораторної роботи я освоїв фундаментальну абстрактну структуру даних черга, дослідження динаміки його вмісту та використав ці знання для виконання прикладних програм.
